package arrAndstr;

import java.util.Arrays;

/*
	105. 从前序与中序遍历序列构造二叉树
	优化思路：
		用hash优化index()查找下标的O(n)
 */
public class T105 {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public static void main(String[] args) {
		int[] preorder = new int[]{3,9,20,15,7}, inorder = new int[]{9,3,15,20,7};

		TreeNode root = buildTree(preorder, inorder);

	}

	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		TreeNode root = new TreeNode(preorder[0]);
		int valueIndex = getNumIndex(inorder, preorder[0]);

		if (valueIndex > 0) {
			root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + valueIndex), Arrays.copyOfRange(inorder, 0, valueIndex));
		}
		if (1+valueIndex <= preorder.length-1) {
			root.right = buildTree(Arrays.copyOfRange(preorder, 1 + valueIndex, preorder.length), Arrays.copyOfRange(inorder, valueIndex+1, inorder.length));
		}

		return root;
	}

	private static int getNumIndex(int[] inorder, int num) {
		for (int i = 0; i < inorder.length; i++) {
			if (inorder[i] == num)	return i;
		}
		return 0;
	}

}

